431C - k-Tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl "\n"
const ll N = 1e9+7;

ll lcm(ll a, ll b) 
{ 
    return a / __gcd(a, b) * b; 
}

ll binpow(ll a, ll b,ll mod)
{
    a %= mod;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void dfs_trav(ll node,vector <ll> *graph,ll *vis,vector <ll> &dfs)
{
    for(auto it : graph[node])
    {
        if(!vis[it])
        {
            dfs.push_back(it);
            vis[it]=1;
            dfs_trav(it,graph,vis,dfs);
        }
    }
}

void bfs_trav(ll node,vector <ll> *graph,ll *vis,vector <ll> &bfs)
{
    queue <ll> qu;
    qu.push(node);
    while(!qu.empty())
    {
        ll node = qu.front();
        qu.pop();
        bfs.push_back(node);
        for(auto it : graph[node])
        {
            if(!vis[it])
            {
                vis[it]=1;
                qu.push(it);
            }
        }
    }
}

ll fun(ll n,ll k,ll d,ll flag,vector <vector <ll>> &dp)
{
	if(n<=0)
		return flag;
	if(dp[n][flag]!=-1)
		return dp[n][flag]%N;
	ll sum = 0;
	for(ll i = 1; i <= k; ++i)
	{
		if(i>n)
			break;
		if(i<d)
		{
			dp[n-i][flag]=fun(n-i,k,d,flag,dp)%N;
			sum+=dp[n-i][flag];
			sum%=N;
		}
		else
		{
			dp[n-i][1]=fun(n-i,k,d,1,dp)%N;
			sum+=dp[n-i][1];
			sum%=N;
		}
	}
	return sum%N;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t=1;
    // cin >> t;
    while(t--)
    {    
        ll a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0,m=0,n=0,o=0,q=0,u=0,v=0,w=0,x=0,y=0,z=0,sum=0,res=0,ans=0,rem=0,ct=0,maxim=0,minim=0;
        string p,r,s,str;
        cin >> n >> k >> d;
        vector <vector <ll>> dp(n+1 , vector <ll> (2,-1));
        cout << fun(n,k,d,0,dp) << endl;
        //ll arr[n];
        // for(ll i = 0; i < n; ++i)
        // {
        //     cin >> arr[i];
        // }
        // vector <pair<ll,ll>> vp;
        // vector <pair<pair<ll,ll>,ll>> vpp;
        // map <pair<ll,ll>,ll> mpp;

        // ---------------- VECTOR INPUT ---------------------------
        // vector <ll> vec;
        // for(ll i = 0; i < n; ++i)
        // {
        //     cin >> x;
        //     vec.push_back(x);
        // }

        // ---------------- MAP INPUT ---------------------------
        // map <ll,ll> mp;
        // for(ll i = 0; i < n; ++i)
        // {
        //     cin >> arr[i];
        //     mp[arr[i]]++;
        // }

        // ---------------- PREFIX SUM ---------------------------
        // ll hsh[n];
        // hsh[0]=arr[0]; 
        // for(ll i = 1; i < n; ++i)
        // {
        //      hsh[i]=hsh[i-1]+arr[i];
        // }

        // ---------------- SUFFIX SUM ---------------------------
        // hsh[n-1]=arr[n-1]; 
        // for(ll i = n-1; i >= 0; --i)
        // {
        //      hsh[i]=hsh[i+1]+arr[i];
        // }

        // ----------------UNDIRECTED GRAPH INPUT ---------------------------
        // cin >> n >> m;
        // vector <ll> graph[n+1];
        // for(ll i = 0; i < m; ++i)
        // {
        //     cin >> u >> v;
        //     graph[u].push_back(v);
        //     graph[v].push_back(u);
        // }
        
        // ----------------DIRECTED GRAPH INPUT ---------------------------
        // cin >> n >> m;
        // vector <ll> graph[n+1];
        // for(ll i = 0; i < m; ++i)
        // {
        //     cin >> u >> v;
        //     graph[u].push_back(v);
        // }

        // ---------------- BFS TAVERSAL ---------------------------
        // vector <ll> bfs;
        // ll vis[n+1] = {0};
        // ll root = 1;
        // vis[root]=1;
        // bfs_trav(root,graph,vis,bfs);

        // ---------------- DFS TAVERSAL ---------------------------
        // vector <ll> dfs;
        // ll vis[n+1] = {0};
        // ll root = 1;
        // vis[root]=1;
        // dfs.push_back(root);
        // dfs_trav(root,graph,vis,dfs);
        
    }
    return 0;
}